#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void qsort(vector<int>& nums,int  l,int r) {
	if (l >= r) return;
	int key = nums[l + rand() % (r-l + 1)];
	int i = l, left = l - 1, right = r + 1;
	while (i < right) {
		if (nums[i] < key) swap(nums[++left], nums[i++]);
		else if (nums[i] == key) ++i;
		else swap(nums[--right], nums[i]);
	}
	qsort(nums, l, left);
	qsort(nums, right, r);
}


void Sort(vector<int>& nums) {
	srand(time(nullptr));
	qsort(nums,0,nums.size()-1);
}

int main() {
	vector<int> nums{ 5,1,2,2,2,4,6,8,8,9,3 };
	Sort(nums);
	for (auto x : nums) {
		cout << x << " ";
	}
	cout << endl;
	return 0;
}
